#pragma once

#include <vector>
#include <assert.h>
#include <cstddef>

using std::pair;

template <class Key, class Value>
class CuckooHash {
public: 
	static const unsigned int HASH_SIZE = 1024;
	static const unsigned int TABLES_COUNT = 2;
	static const unsigned int MAX_INS_ATTEMPT_COUNT = 256;
	typedef unsigned int hash_t;

	typedef hash_t (*hash_func_t)(const Key& elem);
	
	CuckooHash(hash_func_t hash_func[TABLES_COUNT]);
	~CuckooHash();

	bool Insert(const Key& key, const Value& value);
	const Value* Find(const Key& elem);
	void RemoveAll(const Key& elem);

protected:
	bool ReplaceWith(const pair<Key, Value> *new_pair, unsigned int table_index); 

	hash_func_t hash_func_[TABLES_COUNT];
	pair<Key, Value> *table_[TABLES_COUNT][HASH_SIZE]; // Each table may contain only one element 

	
};

template <class Key, class Value>
CuckooHash<Key, Value>::CuckooHash(hash_func_t hash_func[TABLES_COUNT]) {
	for (int i = 0; i < TABLES_COUNT; ++i) {
		for (int j = 0; j < HASH_SIZE; ++j)
			table_[i][j] = NULL;

		assert(hash_func[i] != NULL);
		hash_func_[i] = hash_func[i];
	}
}

template <class Key, class Value>
CuckooHash<Key, Value>::~CuckooHash() {
	for (int i = 0; i < TABLES_COUNT; ++i) {
		for (int j = 0; j < HASH_SIZE; ++j)
			if (table_[i][j]) {
				delete[] table_[i][j];
				table_[i][j] = NULL;
			}
		hash_func_[i] = NULL;
	}
}

template <class Key, class Value>
bool CuckooHash<Key, Value>::Insert(const Key& key, const Value& value) {
	
	pair<Key, Value> *new_elem = new pair<Key, Value> (key, value);
	return ReplaceWith(new_elem, 0);
}

template <class Key, class Value>
bool CuckooHash<Key, Value>::ReplaceWith(const pair<Key, Value> *new_pair, unsigned int table_index) {
	assert(new_pair != NULL);
	pair<Key, Value> *old = NULL;
	for (unsigned int i = 0; old != NULL; ++i) {
		if (i >= MAX_INS_ATTEMPT_COUNT)
			return false;
		assert(table_index < TABLES_COUNT);
		assert(hash_func_[table_index] != NULL);

		hash_t hash = hash_func_[table_index] (new_pair->first) % HASH_SIZE;
		
		old = table_[table_index][hash];
		table_[table_index][hash] = new_pair;
		
		table_index = (table_index + 1) % 3;
		new_pair = old;

	}	
	return true; 
}

template <class Key, class Value>
const Value* CuckooHash<Key, Value>::Find(const Key& elem) {
	for (unsigned int i = 0; i < TABLES_COUNT; ++i) {
		assert(hash_func_[i] != NULL);
		hash_t hash = hash_func_[i](elem);
		if (table_[i][hash] && table_[i][hash]->first == elem) 
			return &(table_[i][hash]->second);
	}
	return NULL;
}

template <class Key, class Value>
void CuckooHash<Key, Value>::RemoveAll(const Key& elem) {
	for (unsigned int i = 0; i < TABLES_COUNT; ++i) {
		assert(hash_func_[i] != NULL);
		hash_t hash = hash_func_[i](elem);
		if (table_[i][hash] && table_[i][hash]->first == elem) {
			delete [] table_[i][hash];
			table_[i][hash] = NULL;
		}
	}
}
